package com.example.interview.bean.tree;

/**
 * @author ：superdyf
 * @date ：Created in 2021/10/11 15:12
 * @description：
 * @modified By：
 */
public class Tree<E extends Comparable<E>> {
    public TreeNode<E> root;

    public Tree(TreeNode<E> root) {
        this.root = root;
    }
    /**
     * @Author superdyf
     * @Description //TODO 递归
     * @Date 15:16 2021/10/13
     * @Param [e]
     * @return void
     **/
    public void insertByRecursion(E e){
        inRecursion(root,new TreeNode<>(e));
    }
    public TreeNode<E> finadByRecursion(E e){
       return  find(root,new TreeNode<>(e));
    }
    public void inRecursion(TreeNode<E> parent,TreeNode<E> e){
        TreeNode<E> current;
        if(Integer.toUnsignedLong(e.getE().hashCode()) < Integer.toUnsignedLong(parent.getE().hashCode())){
            if((current=parent.getLeft())==null){
                parent.setLeft(e);
            }
        }else{
            if((current=parent.getRight())==null){
                parent.setRight(e);
            }
        }
        if(null!=current){
            inRecursion(current,e);
        }
    }
    public void insert(E e){
        TreeNode<E> n=new TreeNode<>(e);
        TreeNode<E> current=root;
        // 上个节点
        TreeNode<E> parent  = null;
        if(null==current){
            root=n;
        }
        int lh=0,rh=0,height=0;
        while (true) {
            parent = current;
            height++;
            if (Integer.toUnsignedLong(e.hashCode()) < Integer.toUnsignedLong(current.getE().hashCode())) {
                lh++;
                if ((current = current.getLeft()) == null) {
                    n.setHeight(height);
                    n.setOffset(lh);
                    n.setDleft(-1);
                    parent.setLeft(n);
                    break;
                }
            } else {
                rh++;
                if ((current = current.getRight()) == null) {
                    parent.setRight(n);
                    n.setHeight(height);
                    n.setDleft(1);
                    n.setOffset(rh);
                    break;
                }
            }
        }
    }
    public E find(E e){
        TreeNode<E> tmp  = root;
        while (true) {
            if(tmp!=null){
                if(e.hashCode()==tmp.getE().hashCode()){
                    return tmp.getE();
                }
                if (Integer.toUnsignedLong(e.hashCode()) < Integer.toUnsignedLong(tmp.getE().hashCode())) {
                    tmp = tmp.getLeft();
                } else {
                    tmp = tmp.getRight();
                }
            }
        }
    }
    public TreeNode<E> find(TreeNode<E> root,TreeNode<E> e){
        if(null==root)return null;
        TreeNode<E> current=root;
        if(root.getE().hashCode()==e.getE().hashCode()){
            return root;
        }
        if(Integer.toUnsignedLong(e.getE().hashCode()) < Integer.toUnsignedLong(current.getE().hashCode())){
            current=root.getLeft();
        }else{
            current=root.getRight();
        }
       return find(current,e);
    }
}
